#include"main.h"
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
void create_tree(BiTreeNode **root_pp,char *pre_order_seq,int num_elements) {
    static int index = 0;
    if(index >= num_elements) {
        return;
    }
    if(pre_order_seq[index] == '#') {
        (*root_pp) = NULL;
        index++;
        return;
    }
    *root_pp = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    if(*root_pp == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    (*root_pp)->data = pre_order_seq[index];
    index++;
    create_tree(&(*root_pp)->leftChild,pre_order_seq,num_elements);
    create_tree(&(*root_pp)->rightChild,pre_order_seq,num_elements);
}
void pre_order_traverse(BiTreeNode *t,void visit(DataType item)) {
    if(t != NULL) {
        visit(t->data);
        pre_order_traverse(t->leftChild,visit);
        pre_order_traverse(t->rightChild,visit);
    }
}
void in_order_traverse(BiTreeNode *t,void visit(DataType item)) {
    if(t != NULL) {
        in_order_traverse(t->leftChild,visit);
        visit(t->data);
        in_order_traverse(t->rightChild,visit);
    }
}
void post_order_traverse(BiTreeNode *t,void visit(DataType item)) {
    if(t != NULL) {
        post_order_traverse(t->leftChild,visit);
        post_order_traverse(t->rightChild,visit);
        visit(t->data);
    }
}
BiTreeNode *search(BiTreeNode *root,DataType x) {
    if(root == NULL) {
        return NULL;
    }
    if(root->data == x) {
        return root;
    }
    BiTreeNode *left_result = search(root->leftChild,x);
    if(left_result != NULL) {
        return left_result;
    }
    return search(root->rightChild,x);
}
void Visit(DataType item) {
    printf("%c",item);
}
void destory(BiTreeNode **root) {
    if(*root != NULL) {
        destory(&(*root)->leftChild);
        destory(&(*root)->rightChild);
        free(*root);
        *root = NULL;
    }
}
int main() {
    char *pre_order_seq = "ABC##DE#G##F###";
    BiTreeNode *root = NULL;
    int num_elements = strlen(pre_order_seq);
    int index = 0;
    create_tree(&root,pre_order_seq,num_elements);
    printf("先序遍历：");
    in_order_traverse(root,Visit);
    printf("\n");
    printf("后序遍历：");
    post_order_traverse(root,Visit);
    printf("\n");
    destory(&root);
    return 0;
}